#include <iostream>
#include <stdlib.h>
#include <time.h>
#include "../include/mergesort.h"

using namespace std;

// 归并排序
// 1. 和快速排序类似，都是分治法；不同之处在于，快排是在递的过程中排序，而归并排序则是在归的过程中合并排序
// 2. 归并排序的过程
//     1. 递归边界：当数组长度为1时，递归结束
//     2. 递归过程：切分结束后，进行归并

// 3. 归并排序的复杂度
//     1. 时间复杂度： nlogn
//     2. 空间复杂度： O(n)   实际上是 O(n) + O(logn) 其中logn是递归栈的深度
//     3. 稳定性： 稳定
//     4. 最优时间复杂度：nlogn
//     5. 最差时间复杂度: nlogn  (递归每次都是二分)


void Merge(int arr[], int left, int mid, int right) {
    int* tmp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;

    // 每次归并的时候都假设左右两个数组都是有序的，因为上一次归并已经排好的
    // 所以只需要比较左右两个数组的元素，将较小的元素放入临时数组中，而不用再次在左右两个数组之间进行比较
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }

    // 将剩余的元素放入临时数组中，也是因为上一次归并已经排好的，直接放入即可
    while (i <= mid)
        tmp[k++] = arr[i++];
    while (j <= right)
        tmp[k++] = arr[j++];

    for (int i = 0; i < k; i++)
        arr[left + i] = tmp[i];
    
    delete [] tmp;
    tmp = nullptr;
}


void MergeSort(int arr[], int left, int right) {
    if (left >= right)
        return;

    MergeSort(arr, left, (left + right) / 2);
    MergeSort(arr, (left + right) / 2 + 1, right);
    Merge(arr, left, (left + right) / 2, right);
}

void MergeSort(int arr[], int size) {
    if (size <= 1)
        return;

    MergeSort(arr, 0, size - 1);
}


// int main(int argc, const char** argv) {
//     int arr[10];
//     srand(time(NULL));
//     for (int i = 0; i < 10; i++) {
//         arr[i] = rand() % 100;
//         cout << arr[i] << " ";
//     }
//     cout << endl;

//     MergeSort(arr, 10);
//     for (int val : arr)
//         cout << val << " ";
//     cout << endl;
//     return 0;
// }